package greedy

import (
	"sort"
	"strings"
)

type MyStringSlice []string
func (x MyStringSlice) Len() int           { return len(x) }
func (x MyStringSlice) Less(i, j int) bool { return x[i]+x[j] < x[j]+x[i]}
func (x MyStringSlice) Swap(i, j int)      { x[i], x[j] = x[j], x[i] }

func GetMinDictSortStr(strs []string) string{
	if len(strs) == 0{ return "" }
	var allpath []string
	fn := func(path string) {
		allpath = append(allpath, path)
	}
	GetMinProcess1(strs, map[int]struct{}{}, []string{}, fn)
	minStr := allpath[0]
	for i:=1; i<len(allpath); i++ {
		if minStr > allpath[i] {
			minStr = allpath[i]
		}
	}
	return minStr
}

func GetMinProcess1(strs []string, used map[int]struct{}, path []string, fn func(path string)){
	if len(used) == len(strs) {
		fn(strings.Join(path, ""))
		return
	}
	for i, v := range strs {
		if _, ok := used[i]; ok {
			continue
		}
		used[i] = struct{}{}
		path = append(path, v)
		GetMinProcess1(strs, used, path, fn)
		delete(used, i)
		path = path[:len(path)-1]
	}
}

func GetMinDictSortStr2(strs []string) string{
	sort.Sort(MyStringSlice(strs))
	return strings.Join(strs, "")
}